\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc} % encoding
\usepackage[ngerman]{babel} % language
\usepackage{graphicx}
\usepackage{listings}
\usepackage{textpos}
\usepackage{longtable}
\usepackage[usenames,dvipsnames]{color} 

\definecolor{darkblue}{RGB}{0,32,97}			%custom colors for coloring inside listing
\definecolor{darkgreen}{RGB}{27,189,8}

\lstset{ 									%set parameters for code 
  language=C,              			 		% the language of the code
  basicstyle=\footnotesize,          		% the size of the fonts that are used for the code
  identifierstyle=,                   		% the step between two line-numbers. If it's 1, each line 
  keywordstyle=\color{darkblue}\bfseries,  	% keyword coloring
  commentstyle=\color{darkgreen},       			% comment coloring
  stringstyle=\color{blue},        	 		% string coloring
  showstringspaces=false,
  tabsize=3,
  escapeinside={(@}{@)},						%escape-pattern inside listing
%emph={READC,PRINTC,READI,PRINTI,define},emphstyle=\color{darkgreen}, %define custom keywords
}

\begin{document}

\title{\textbf{Primeval\\\Large{Dokumentation}}}
\author{Christoph Linecker \and Johannes Mory\and Sebastian Zanner}
\date{}

\maketitle
\thispagestyle{empty} 						%hide page number
\newpage

\tableofcontents
\thispagestyle{empty}
\newpage

\part*{Überblick}
\addcontentsline{toc}{part}{Überblick}

\section*{Einleitung}
\addcontentsline{toc}{section}{Einleitung}

\textit{Primeval} ist ein Compiler. Dieser Compiler kompiliert, in einer modifizierten Untermenge von C geschriebene, Source-Dateien. Definiert wurde diese Sprache in Extended Backus Naur Form.  Source Dateien haben per Konvention die Endung 'pv', es werden aber auch Dateien mit abweichendem Suffix verarbeitet. Die Ausgabesprache sind binär kodierte Assemblerinstruktionen für einen Emulator eines RISC-Prozessors (DLX Architektur).

\section*{Features}
\addcontentsline{toc}{section}{Features}

\begin{itemize}
	\item Grundtypen 
	\item Arrays 
	\item Records 
	\item Type-Definitions 
	\item Arithmetische Ausdrücke
	\item Boolsche Ausdrücke 
	\item Lazy Evaluation von Boolschen Ausdrücken
	\item Kontrollstrukturen
	\item Prozeduren
	\item Error-Handling
\end{itemize}

\part*{EBNF}
\addcontentsline{toc}{part}{EBNF}

\section*{Scanner\\}

\begin{tabular}{p{3cm} p{1cm} p{12cm}}
	identifier & = & letter \{letter $|$ digit\}. \\\\
	integer & = & digit \{digit\}.\\\\
	string & = & "$"$" \{printableCharacter\} "$"$".\\\\
	comment & = & ''/*'' \{printableCharacter\} ''*/''.\\\\	
	simpleSymbol & = & '';'' $|$ '','' $|$ ''('' $|$ '')'' $|$ ''\{'' $|$ ''\}'' $|$ ''['' $|$ '']'' $|$\\
			&   & ''='' $|$ ''*'' $|$ ''/'' $|$ ''\%'' $|$ ''$+$'' $|$ ''$-$'' $|$\\ 
			&   & ''$<$'' $|$ ''$>$'' $|$ ''$<=$'' $|$ ''$>=$''.\\\\			
	keyword & = & ''and'' $|$ ''or'' $|$ ''equ'' $|$ ''neq' $|$ ''if'' $|$ ''else'' $|$ ''while'' $|$\\
			&   & ''char'' $|$ ''int'' $|$ ''bool'' $|$ ''struct'' $|$ ''function'' $|$ ''const'' $|$\\
			&   & ''typedef'' $|$ ''sequence'' $|$ ''involve'' $|$ ''return'' $|$ ''new'' $|$\\
			&   & ''ptr'' $|$ ''true'' $|$ ''false''.\\ 	
\end{tabular}

\section*{Parser\\}

\hspace*{-2.5cm}									%hack to decrease page margins (e.g. large images/tables)
\begin{tabular}{p{3cm} p{1cm} p{13cm}}
	primeval & = & ''\{''involve''\}'' sequence statementSequence.\\
	involve & = & ''involve'' identifier sequenceSelector '';''.\\
	sequenceSelector & = & ''\{''.'' identifier\}.\\
	sequence & = & ''sequence'' sequenceList '';''.\\
	sequenceList & = & identifier \{''.'' identifier\}.\\
	statementSequence & = & \{declaration $|$ procedureDeclaration\}.\\
	\\
	expression & = & simpleExpression [( ''equ'' $|$ ''neq'' $|$ ''$<$'' $|$ ''$>$'' $|$ ''$<=$'' $|$ ''$>=$'' ) 								 simpleExpression].\\
	simpleExpression& = & [''$+$'' $|$ ''$-$''] term \{(''$+$'' $|$ ''$-$'' $|$ ''or'') term\}.\\
	term & = & factor \{(''*'' $|$ ''/'' $|$ ''\%'' $|$ ''and'' ) factor\}.\\
	factor & = & (identifier selector) $|$ integer $|$ character $|$ (''('' expression '')'') $|$\\
	 	   &   & string $|$ (procedureCall selector) $|$ type.\\
	\\
	statement & = & declaration $|$ assignment $|$ procedureCall $|$ ifStatement $|$ whileStatement $|$ return.\\
	ifStatement 	& = & ''if'' ''('' expression '')'' body \{''elif'' ''('' expression '')'' body\}[''else'' body].\\
	whileStatement & = & ''while'' ''('' expression '')'' ''{'' body ''}''.\\
	body & = & ''\{'' \{statement\} ''\}''.\\
	\\
	assignment & = & identifier selector ''='' expression '';''.\\
	procedureDeclaration & = & ''function'' type identifier ''('' [formalParameters] '')'' body '';''.\\
	formalParameters & = & type identifier \{'','' type identifier\}.\\
	actualParameters & = &''(''[expression \{'','' expression\}]'')''.\\
	return & = & ''return'' [expression] '';''.\\
	procedureCall & = & identifier actualParameters '';''.\\
	selector & = & \{''-$>$'' identifier $|$ ''[''expression'']''\}.\\
	\\

	declaration & = & (([''const''] type identifier [''='' expression]) $|$ structure $|$ typedeclaration) '';''.\\
	typedeclaration & = & ''typedef'' type identifier '';''.\\
	fieldDeclaration& = & fieldType identList.\\
	\\
	type & = & (''char'' $|$ ''int'' $|$ ''bool'' $|$ structType $|$ identifier) \{''ptr''\}.\\
	fieldType & = & ''char'' $|$ ''int'' $|$ ''bool'' $|$ structType \{''ptr''\}.\\
	structType & = & ''struct'' identifier ''ptr''.\\
	structure & = &  ''struct'' identifier ''\{''  fieldDeclaration '';'' \{fieldDeclaration '';''\} ''\}'' '';''.\\
	\\	
	identifier & = & letter \{letter $|$ digit\}.\\
	integer & = & digit \{digit\}.\\
	character & = & "$'$"char"$'$".\\
	\\
	letter & = & ''a'' $|$ ''b'' $|$ ... $|$ ''z'' $|$ ''A'' $|$ ''B'' $|$ ... $|$ ''Z''.\\
	digit & = & ''0'' $|$ ''1'' $|$ ''2'' $|$ ''3'' $|$ ''4'' $|$ ''5'' $|$ ''6'' $|$ ''7'' $|$ ''8'' $|$ ''9''. 		
\end{tabular}

\part*{Der Compiler}
\addcontentsline{toc}{part}{Der Compiler}

\section*{Komponenten \& Beziehungen}
\addcontentsline{toc}{section}{Komponenten \& Beziehungen}
\vspace{0.75cm}

\centerline{\includegraphics[scale=0.65]{diagramm.pdf}}		%use \centerline for large images

\section*{Aufbau}

\begin{itemize}
	\item Scanner (.c/.h) 
	\item Parser (.c/.h)
	\item SymbolTable (.c/.h)
	\item CodeGenerator (.c/.h)
	\item VirtualMachine (.c/.h)
\end{itemize}

\section*{Scanner}
\addcontentsline{toc}{section}{Scanner}

Der Scanner ist Teil des Front-Ends unseres/eines Compilers und zuständig für die lexikalische Analyse eines Programmes. Er übersetzt die übergebenen Textdatei in eine Abfolge von zuvor definierten Symbolen und stellt dem, mit der Syntaxanalyse beauftragtem, Parser eine Schnittstelle zur Verfügung, mit der diese abgerufen werden können. Dieses Prinzip ist - der Vorlesung folgend - folgendermaßen umgesetzt:\\

\noindent Es gibt eine globale Variable ''\textit{currentKey}'' vom Typ:

\begin{center}
\begin{tabular}{|c|}
\hline
\begin{lstlisting}
struct key
{
	int		symbol;	//~eindeutige Id
	int		length;	//~die Zeichenlaenge des Symbols
	string_t	value;	//~die Zeichenkette des Symbols
	int		line, column;	//~die Position des Symbols
}
\end{lstlisting}\\

\hline
\end{tabular}
\end{center}
\noindent Beim Aufrufen der Schnittstellen-Methode ''\textit{get()}''liest der Scanner die Quelltext-Datei genau solange Zeichen für Zeichen ein, bis eine Zeichenabfolge als definiertes Symbol erkannt wird, und befüllt ''\textit{currentKey}'' entsprechend, sodass das aktuelle Symbol vom Parser abgerufen werden kann.\\

\noindent Der Scanner erkennt also

\begin{itemize}
	\item welche Zeichen gültig sind,
	\item welche Zeichen(ketten) welche Symbole repräsentieren,
	\item welche Zeichen Whitespace darstellen,
	\item welche Zeichenabfolgen auf den Anfang bzw. das Ende eines Kommentars hinweisen,
	\item wann die Textdatei zu Ende ist
\end{itemize}

\noindent und reagiert entsprechend, d.h.

\begin{itemize}
	\item er gibt Fehlermeldungen (inkl. Position) aus,
	\item überprüft, ob ''\textit{Identifier}'' einem Keyword entsprechen,
	\item überspringt Leerzeichen, Absätze, Tabs und Kommentare
	\item zeigt dem Parser an, wenn das Ende des Quelltextes erreicht ist.
\end{itemize}

\section*{Parser}
\addcontentsline{toc}{section}{Parser}

Für diesen Compiler haben wir einen \textit{top-down}, \textit{recursive-descent} Parser implementiert. 

\subsection*{Syntaxanlayse} 

Grundlage der Syntaxanalyse ist die in der EBNF definierte Syntax unserer Eingabesprache. Bei der Syntaxanalyse prüft der Parser ob der, durch Scannertokens repräsentierte, Quelltext den syntaktischen Regeln unserer Sprache genügt. Für jedes Nicht-Terminalsymbol in unserer EBNF wurde eine gleichnamige Prozedur implementiert, welche der Parser aufruft wenn er in einer \textit{production rule} auf ein Nicht-Terminalsymbol stößt. Unser Parser implementiert ein \textit{pushdown automaton}, also eine \textit{finite state machine} erweitert mit einem Stack. Der Stack ist in diesem Fall der Call-Stack der aufgerufenen Prozeduren für die Nicht-Terminalsymbole.\\  


\part*{Features}
\addcontentsline{toc}{part}{Features}

\section*{Kontrollstrukturen}
\addcontentsline{toc}{section}{Kontrollstrukturen}
Primeval beherrscht sowohl Wenn-Dann-Kontrollstrukturen als auch einfache Schleifen.

\subsection*{IF-ELSE}
\addcontentsline{toc}{subsection}{IF-ELSE}

Ein If-Statement beginnt immer mit dem Terminalsymbol ''\textit{if}'', es folgen eine in Klammern gesetzte Bedingung sowie eine Sequenz von Befehlen für den Fall, dass diese Bedingung wahr ist - das anschließende ''\textit{else}'' ist optional.\\

\noindent Die Umsetzung in Primeval orientiert sich stark an der Vorlesung und soll hier nur skizziert werden:

\begin{itemize}
\item Sobald der Parser ein ''\textit{if}''-Symbol liest, wird die folgende Bedingung ausgewertet und das Ereignis in ein freies Register geladen. Anschließend wir ein Branch-Befehl emittiert, der genau dann auslöst, wenn die gegebene Bedingung falsch auswertet und also genau dorthin springen muss, wo ''\textit{if}'' aufhört oder ein wahlweiser ''\textit{else}''-Fall anfängt. Wertet die Bedingung hingegen wahr aus, soll der ''\textit{else}''-Fall übersprungen werden - es muss daher an den Körper des ''\textit{if}''-Falles ein Branch emittiert werden, der genau dies tut.
\end{itemize}

\subsection*{WHILE}
\addcontentsline{toc}{subsection}{WHILE}

Eine While-Schleife fängt mit dem ''\textit{while}''-Symbol an, auf das ebenfalls eine Bedingung folgen muss. Auch hier ist im Primeval-Parser die in der Vorlesung vorgestellte Methode implementiert:\\

\noindent Analog zur If-Kontrollstruktur wird nach dem Lesen eines ''\textit{while}''-Terminals eine Bedingung ausgewertet und deren Ergebnis in ein Register geladen. Es folgt ein Branch der den Schleifen-Körper überspringt, sofern die Bedingung nicht erfüllt wird. An den Körper selbst wird ein Branch angehängt der stets an die Stelle zurückspringt an der die Schleifen-Bedingung ausgewertet wird - wenn die Bedingung schließlich nach falsch auswertet, wird dieser Branch vom Ersten übersprungen und der Schleifen-Körper nicht mehr ausgeführt.\\
	
\noindent Für beide Strukturen ergibt sich aus den jeweiligen Methoden ein ähnliches Problem:\\

\noindent Zu dem Zeitpunkt, zu dem bestimmte Branch-Befehle erzeugt werden (''\textit{if}''-Fall, ''\textit{else}''-Fall oder Schleifen-Körper überspringen) ist nicht klar wie weit gesprungen werden muss, weil nicht vorhergesagt werden kann wie lange der folgende Körper sein wird. Deshalb wird, nachdem der jeweilige Körper geparst worden ist, und gleichsam die notwendige Sprungweite bestimmbar, diese nachträglich mit dem vorgestellten Fix-Up-Chain-Prinzip in den Branch-Befehlen verändert.
\end{itemize}

\section*{Virtual Machine}
\addcontentsline{toc}{section}{Virtual Machine}

Die VM wurde von uns in \textit{C} implementiert und ist in der Lage DLX-Instruktionen zu dekodieren und auszuführen. Das Format der Instruktionen wurde ohne Abweichungen aus der Vorlesung übernommen. Die Instruktionen werden im Code Generator als 32-Bit Integer enkodiert und in eine Datei geschrieben.\\

\noindent Nachdem die VM gestartet wurde, lädt sie zunächst das gesamte Programm (= enkodierte DLX-Instruktionen) in ihren Speicher und setzt den Global-Pointer auf die Größe des Programms. Um die Instruktionen zu dekodieren liest die VM jeweils 4 Felder aus dem Array, beginnend beim Programm-Counter (ein Index in das Array).\\ 

\noindent Um das Format der Instruktion schnell erkennen zu können, haben wir die verschiedenen Instruktionen so nummeriert, dass alle Instruktionen im Format F1 zwischen 1 und 22 liegen und alle Instruktionen im Format F2 zwischen 23 und 33. Die einzelnen Felder der Instruktion werden durch \textit{shift} und \textit{and} Verknüpfung auf Bit-Basis extrahiert. Ein Switch über die Operationsnummer identifiziert die entsprechende Instruktion, welche anschließend ausgeführt wird.\\

\hspace*{-1.25cm}
\begin{tabular}{| c | c |}
	\hline
	\lstinline|unsigned char *vm_memory|
	& 
	Speicher (32,000) $|$ Byte-adressiert \\
	\hline
	\lstinline|unsigned long *instruction| &  enkodierte Instruktion\\
	\hline
	\lstinline|int runVirtualMachine(int d, char *fileName)| & startet VM\\
	\hline
	\lstinline|if(vm_reg[STACKPOINTER] == MEMORYSIZE-1)| & VM terminiert, falls diese Bedingung\\
	& nach POP Instruktion erfüllt ist\\
	\hline
\end{tabular}\\

\begin{center}
	\fbox{
		\includegraphics[scale=0.5]{vmMemory.pdf}
	}}   
\end{center}

\begin{center}
	\fbox{
		\includegraphics[scale=0.5]{instruction_formats.pdf}
	}}   
\end{center}


\part*{Features}
\addcontentsline{toc}{part}{Features}

\subsection*{If-then-Else}
\addcontentsline{toc}{part}{Features}


\newpage
\part*{Demo-Programme}
\addcontentsline{toc}{part}{Demo-Programme}

\begin{center}
	\fbox{\parbox{7.5cm}{
	\centering{\large{Sämtliche Demo-Programme werden mit\\ \textbf{\textit{make [Programmname]}}\\ compiliert und mit\\ 	\textbf{\textit{./[Programmname]}}\\ ausgeführt.}}
	}}
\end{center}

\section*{Name: Demo-Programm0.pv1\\Feature: was wird demonstriert ...}

\paragraph*{Beschreibung:}
Programmbeschreibung ...








\end{document}